package leetcode_1100;

import java.util.Arrays;

/**
 *@author 周杨 
 *LongestStringChain_1048 给一个数组 构成一个序列 这个字符串每一个相邻的元素都要满足 前一个字符串在任意位置增加一个字符等于下一个字符串
 *describe:常规题 动态规划
 *2019年5月24日 上午11:30
 */
public class LongestStringChain_1048 {
	public static void main(String[] args) {
		LongestStringChain_1048 test = new LongestStringChain_1048();
		String[] input = new String[] {"ksqvsyq","ks","kss","czvh","zczpzvdhx","zczpzvh","zczpzvhx","zcpzvh","zczvh","gr","grukmj","ksqvsq","gruj","kssq","ksqsq","grukkmj","grukj","zczpzfvdhx","gru"};
		System.out.println(test.longestStrChain(input));
	}
	
	public int longestStrChain(String[] words) {
		if(words.length == 1) return 1;
		Arrays.sort(words,(o1,o2)->o1.length()-o2.length());
		int max = 1;
        int[] dp = new int[words.length];
        for(int i=0;i<words.length;++i) {
        	dp[i] = 1;
        	for(int j=i-1;j>=0;--j) {
        		if(words[i].length() == words[j].length()+1) {
        			if(help(words[j],words[i])) {
        				dp[i] = Math.max(dp[i], dp[j]+1);
        			}
        		}
        	}
        	max = Math.max(max, dp[i]);
        }
        return max;
    }
	
	//ensure a.length = b.length-1
	private boolean help(String a,String b) {
		char[] c1 = a.toCharArray();
		char[] c2 = b.toCharArray();
		int i1=0,i2=0;
		while(i1 < c1.length) {
			if(c1[i1] == c2[i2]) {
				++i1;
				++i2;
			}else {
				if(i1 == i2) {
					++i2;
				}else {
					return false;
				}
			}
		}
		return true;
	}
}
